package com.lsa.skienna.challenge.chap8;

class bishops {
	static boolean finished = false;
	static final int MAXCANDIDATES = 100;
	static final int NMAX = 100;
	static int solution_count = 0;

	static void backtrack(int partialSolution[], int partialSolutionSize, int bishopCount, int deskSize) {
		if (isSolution(partialSolution, partialSolutionSize, deskSize))
			processSolution(partialSolution, partialSolutionSize, deskSize);
		else{
			int candidates[] = new int[MAXCANDIDATES];
			int ncandidates = constructCandidates(partialSolution, ++partialSolutionSize, deskSize, candidates);
			for (int i = 0; i < ncandidates; i++) {
				partialSolution[partialSolutionSize] = candidates[i];
				backtrack(partialSolution, partialSolutionSize, bishopCount, deskSize);
				if (finished)
					return;
			}
		}
	}

	static void processSolution(int partialSolution[], int partialSolutionSize, int deskSize) {
		for (int i = 0; i < deskSize; i++) {
			System.out.print(" _");
		}
		System.out.println();
		for (int i = 1; i <= deskSize; i++) {
			System.out.print("|");
			for (int j = 0; j < deskSize; j++) {
				if (j + 1 == partialSolution[i]) {
					System.out.print('*');
				} else {
					System.out.print('_');
				}
				System.out.print('|');
			}
			System.out.println();
		}
		solution_count++;
		if (solution_count % 1000 == 0) {
			System.out.println(solution_count);
		}
	}

	static boolean isSolution(int partialSolution[], int partialSolutionSize, int deskSize) {
		return partialSolutionSize == deskSize;
	}

	static int constructCandidates(int partialSolution[],
			int incrementedPartialSolutionSize, int deskSize, int candidates[]) {
		boolean isLegalMove = true;
		int ret = 0;
		/* col - possible candidate for the partialSolution, at row=incrementedPartialSolutionSize */
		for (int col = 1; col <= deskSize; col++) // for every possible position at incrementedPartialSolutionSize-row,
										// check whether it is legal move
		{
			isLegalMove = true;
			for (int row = 1; row < incrementedPartialSolutionSize; row++) {
				if (partialSolution[row] == -1) continue;
				if (Math.abs(incrementedPartialSolutionSize - row) == Math.abs(col - partialSolution[row])) 
					/* diagonal threat:
						Namely, on grid two figures stays on diagonal when abs(r1-r2)=abs(c1-c2).
						We have two figures: (incrementedPartialSolutionSize, col) - it is our candidate, and
						(row, partialSolution[row]) - it is solution constructed so far.
						 */
					isLegalMove = false;
			}
			if (isLegalMove) {
				candidates[ret++] = col;
			}
		}
//		candidates[ret++] = -1;
		return ret;
	}

	static public void main(String[] args) {
		int a[] = new int[NMAX];
		backtrack(a, 0, 4, 4);
		System.out.printf("solution_count=%d", solution_count);
	}
}
